package filter

import (
	"math/bits"
	"math/rand"
)
import metro "github.com/dgryski/go-metro"

const maxCuckooCount = 500

type Filter struct {
	bucketSlc []bucket
	count     uint
	bucketPow uint
}

var (
	fpHashes = [256]uint{}
	masks    = [65]uint{}
)

func init() {
	for i := 0; i < 256; i++ {
		fpHashes[i] = (uint(metro.Hash64([]byte{byte(i)}, 1337)))
	}
	for i := uint(0); i <= 64; i++ {
		masks[i] = (1 << i) - 1
	}
}

func MakeFilter(capacity uint) *Filter {
	capacity = getNextPow2(uint64(capacity)) / bucketSize
	if capacity == 0 {
		capacity = 1
	}
	bucketSlc := make([]bucket, capacity)
	return &Filter{
		bucketSlc: bucketSlc,
		count:     0,
		bucketPow: uint(bits.TrailingZeros(capacity)),
	}
}

// LookUp 查找
func (this *Filter) LookUp(data []byte) bool {
	bucketIndex, fp := getIndexAndFingerprint(data, this.bucketPow)
	if this.bucketSlc[bucketIndex].getFingerprintIndex(fp) > -1 {
		return true
	}
	return false
}

// Insert 插入
func (this *Filter) Insert(data []byte) bool {
	bucketIndex, fp := getIndexAndFingerprint(data, this.bucketPow)
	if this.insert(bucketIndex, fp) {
		return true
	}

	fpBucketIndex := getFpHashIndex(fp, bucketIndex, this.bucketPow)
	if this.insert(fpBucketIndex, fp) {
		return true
	}

	// 随机取一个桶索引--用于踢巢
	randVal := rand.Intn(2)
	if randVal == 1 {
		bucketIndex = fpBucketIndex
	}
	return this.reInsert(bucketIndex, fp)
}

// InsertUnique 存在不插入, 不存在插入
func (this *Filter) InsertUnique(data []byte) bool {
	if this.LookUp(data) {
		return false
	}
	return this.Insert(data)
}

// Delete 删除
func (this *Filter) Delete(data []byte) bool {
	bucketIndex, fp := getIndexAndFingerprint(data, this.bucketPow)
	if this.bucketSlc[bucketIndex].delete(fp) {
		this.count--
		return true
	}
	fpBucketIndex := getFpHashIndex(fp, bucketIndex, this.bucketPow)
	if this.bucketSlc[fpBucketIndex].delete(fp) {
		this.count--
		return true
	}
	return false
}

// Count 总数
func (this *Filter) Count() uint {
	return this.count
}

// insert 桶中插入指纹
func (this *Filter) insert(bucketIndex uint, fp byte) bool {
	if this.bucketSlc[bucketIndex].insert(fp) {
		this.count++
		return true
	}
	return false
}

// reInsert 踢巢插入
func (this *Filter) reInsert(bucketIndex uint, fp byte) bool {
	for i := 0; i < maxCuckooCount; i++ {
		entryRandIndex := rand.Intn(bucketSize)
		oldFp := this.bucketSlc[bucketIndex][entryRandIndex]
		this.bucketSlc[bucketIndex][entryRandIndex] = fp
		// 获取被踢出的指纹桶索引
		bucketIndex = getFpHashIndex(oldFp, bucketIndex, this.bucketPow)
		if this.insert(bucketIndex, oldFp) {
			return true
		}
		fp = oldFp
	}
	return false
}

// getIndexAndFingerprint 获取桶索引和指纹值
func getIndexAndFingerprint(data []byte, bucketPow uint) (uint, byte) {
	hash := metro.Hash64(data, 1337)
	fp := getFingerprint(hash)
	// 计算桶索引 %
	bucketIndex := uint(hash>>32) & masks[bucketPow]
	return bucketIndex, fp
}

// getFpHashIndex 获取指纹哈希桶索引值
func getFpHashIndex(fp byte, bucketIndex uint, bucketPow uint) uint {
	mask := masks[bucketPow]
	hash := fpHashes[fp] & mask
	return (bucketIndex & mask) ^ hash
}

// getFingerprint 获取hash的指纹
func getFingerprint(hash uint64) byte {
	fp := byte(hash%255 + 1)
	return fp
}

// getNextPow2 获取桶的指数级容量
func getNextPow2(n uint64) uint {
	n--
	n |= n >> 1
	n |= n >> 2
	n |= n >> 4
	n |= n >> 8
	n |= n >> 16
	n |= n >> 32
	n++
	return uint(n)
}
